import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class num131 {
    //给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案
    public static void main(String[] args) {
        System.out.println(partition("aab").toString());
    }
    public static List<List<String>> partition(String s) {
       List<List<String>> ans = new ArrayList<>();
        int len = s.length();
       if(len == 0) {
           return ans;
       }
       int index = 0;
       List<String > temp = new LinkedList<>();
       dfs(s,index,len,ans,temp);
       return ans;
    }

    private static void dfs(String s, int index, int len, List<List<String>> ans,List<String> temp) {
        if(index == len) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < len; i++) {
            if(!check(s,index,i)) {
                continue;
            }
            temp.add(new String(s.substring(index,i + 1)));
            dfs(s,i + 1,len,ans,temp);
            temp.remove(temp.size() - 1);
        }
    }

    private static boolean check(String s, int index, int i) {
        while (index < i) {
            if(s.charAt(index) != s.charAt(i)) {
                return false;
            }
            i --;
            index ++;
        }
        return true;
    }
}
